The present invention relates to a network priority determining system which, in a network in which various computers, terminals, etc., transmit data to one another, and in which a priority for transmitting terminals is established in such a manner as to efficiently operate the network with a minimized standby time.
A network system in which various computers, terminals, etc., transmit data to one another via a common line or lines requires a system for giving access (transmission rights) to nodes sequentially.
An example of such an access system is a system in which a certain frame (hereinafter referred to as "a free token" when applicable) is circulated through nodes sequentially wherein a node wishing to make a transmission request "catches" the token and changes it into a busy token, which is transmitted with a data packet. As described in IEEE Draft Standard 802.5, "Token Ring Access Method and Physical Layer Specifications", Sept. 23, 1983, a method has been proposed in which the order of priority is given to transmission packets in such a manner that a packet higher in priority is transmitted earlier. This method is carried out as follows:
(1) The token has a priority field P and a reservation field R, and each node writes these levels in respective registers P.sub.r and R.sub.r whenever it receives the token. (The levels contained in the respective fields and registers are designated by the same reference characters for convenience).
(2) If the priority of the free token is P, and the priority level P.sub.m of the transmission request packet of the node is higher than or equal to that of the free token, the free token is changed to a busy token for transmission of the data.
(3) After the packet is transmitted, the node outputs a free token. In this case, the levels of P and R are determined as follows:
(i) for P.sub.r &gt;max (R.sub.r, P.sub.m) PA0 (ii) for P.sub.r &lt;max (R.sub.r, P.sub.m) PA0 (i) In the case of S.sub.r &gt;R.sub.r, PA0 (ii) In the case of R.sub.r &gt;S.sub.r, PA0 (i) the priority of the transmission request packet is lower than that of the network, and PA0 (ii) the level R.sub.r of the reservation of the reservation field is lower than the level of the priority of the transmission request packet. PA0 (i) In the case of P.sub.r &gt;R.sub.r and P.sub.r &gt;P.sub.m, in order to output a free token with P=P.sub.r and R=max (R.sub.r, P.sub.m), comparators (1), (2) and (3) are used to determine the relative levels of P and R. PA0 (ii) In the case of P.sub.r &lt;max (R.sub.r, P.sub.m), in order to output the free token of P=max (R.sub.r, P.sub.m) and R=0, the comparators (1), (2) and (3) are used for decision, to determine the levels of P and R. In this operation, the level of P.sub.r is placed in the stack S.sub.r, and the level of P is placed in the stack S.sub.x. PA0 (i) The circuit 6 determines the levels of S.sub.r and S.sub.x. PA0 (ii) The circuit 6 outputs a selection signal for determining the priority level P and the level R in the reservation field of the token to be transmitted. A data selector 2 operates to select the levels of P and R with the aid of the selection signal from the priority level control circuit 6. The height of the stacks S.sub.r and S.sub.x coincides with the available number of priority levels. PA0 (i) when the comparator 4 determines S.sub.r &gt;R.sub.r, the stack S.sub.x is moved up, a free token with P=S.sub.r and R=P.sub.r is transmitted, and the stack S.sub.r is moved up, PA0 (ii) if S.sub.r &lt;R.sub.r, a free token with P=R.sub.r and R=0 is transmitted, and the level of P is placed in the stack S.sub.x. PA0 (i) Level of priority of the free token: PA0 (ii) Standby time when the level of priority is changed. PA0 (i) Level of priority of the free token: PA0 (ii) Change of the free token: PA0 (iii) Each of the nodes (equal in number to the number of available priority levels) requires two stacks, and therefore the hardware is necessarily intricate. The number of stacks used at all times is no more than (the number of available priority levels).times.2 in the overall network. This means that hardware circuits which are scarcely used must nevertheless be provided.
P=P.sub.r, R=max (R.sub.r, P.sub.m), PA1 P=max (R.sub.r, P.sub.m), R=0,
where P.sub.r is the level held in the priority field register (indicating the present priority level), R.sub.r is the level of the reservation field register, P.sub.m is the priority level of the transmission request packet, P is the set level of the priority field of the transmitting token, R is the set level of the reservation field of the transmitting token, and "0" represents the lowest level of priority.
(4) The node which has increased the level of the priority field in the token stores the original level in a stack S.sub.r and the resultant level in a stack S.sub.x. The number of stacks S.sub.r provided is equal to the available number of priority levels, as is the number of stacks S.sub.x. This node is referred to as a stacking station.
(5) When the stacking station node confirms that none of the nodes have a packet whose level of priority is higher than that of the network outputted by the node, the level of priority is lowered as follows:
the stack S.sub.x is moved up, a token with P=S.sub.r and R=R.sub.r is transmitted, and the stack S.sub.r is moved up. When the stack S.sub.r has been depleted, the stacking station is released.
the stack S.sub.x is moved up, a free token with P=R.sub.r and R=0 is transmitted, and the level of P is placed in the stack S.sub.x. (The stacking station is not changed.)
(6) The reservation field is revised when the following conditions are satisfied:
(7) In order to transmit the free token after the transmission of the data packet, the following operations are carried out:
FIG. 1 is a block diagram showing a priority determining system as described in IEEE Draft Standard 802.5, which is an example of the conventional priority determining system.
In FIG. 1, three registers 1 hold the latest token's priority level and reservation field level and a transmission request packet's priority level. Six comparators 5 are provided for comparison of the contents of the three registers 1 with the contents of stacks 3 and 4.
A priority level control circuit 6 performs the following operations according to the outputs of the comparators 5 and a token output timing signal:
The operation in the case where the stacking station lowers the priority of the network will now be described.
If, in the case where the stacking station has no transmission data packet or the comparator 6 has found P.sub.m =S.sub.x, the comparator 5 determines that the priority level P.sub.r of a received free token is equal to S.sub.x then:
The level of the reservation field is renewed by establishing R=P.sub.m in the case where the comparator 2 has determined R.sub.r .gtoreq.P.sub.m and the comparator 3 has determined P.sub.m .gtoreq.R.sub.r.
As described above, the levels of P and R are selectively determined by the data selector 2 with the aid of the output of the priority control circuit.
The above-described prior art method suffers from the following problems:
If, when the node outputs a free token whose priority is increased, and the present priority P.sub.r of the network is higher than the levels of R.sub.r and P.sub.m, a free token of priority P.sub.r is outputted. If R.sub.r is lower than P.sub.r, the probability is small that a data packet whose priority is higher than P.sub.r is present in other nodes. Therefore, the probability is high that the token will return to the node which has outputted the token, and hence an operation of lowering the priority is carried out.
If a priority of P=max (R.sub.r, P.sub.m) is employed in outputting the free token, the period of time for which the token circulates through the nodes without being caught is decreased, and therefore the efficiency of the network is increased.
It is assumed that the priority level is changed in the order of "1", "2", "3", and "5". These changes mean that the priority of each of the stacking stations is increased by one step in sequence. Therefore, when it is required to lower the priority level "5" of the token to the priority "1", the priority level "5" must be lowered through the priority levels "3" and "2" to reach the priority level "1"; that is, it is impossible to decrease the priority level "5" directly to "1". Therefore, if only a packet having a priority level of "1" exists in the network, then the standby time which elapses until a free token is caught which allows transmission of the packet is about three times as long as in a case where the priority level is changed form "5" directly to "1".
Moreover, the method of determining the priority level according to data from the reservation field in the above-described system suffers from the following problems when the size of a data packet is large compared with the transmission speed of the network, that is, in the case where a long period of time is required for the transmission of the data packet and therefore a new transmission request packet occurs during the period of time:
(1) In the case where, in outputting a free token, the priority level has been determined according to the reservations made by the nodes, a significant period of time has passed after the reservations were made. Therefore, transmission request packets whose priority level are higher than the aforementioned priority level may occur in the nodes. In this case, a packet having higher priority should be dealt with earlier, but it is not.
(2) In the case of data such as audio data which should be especially high in real-time response, the delay characteristic fluctuates, causing distortion in the reproduced sound.
Still further, the above-described prior art system suffers from the following problems:
If, when the node outputs a free token whose priority level is increased, the present priority level P.sub.r of the network is higher than the levels of R.sub.r and R.sub.m, a free token whose priority level is P.sub.r is outputted. If R.sub.r is lower than P.sub.r, the probability is small that a data packet whose priority level is higher than P.sub.r is present in other nodes. Therefore, the probability is high that the token will return to the node which has outputted the token, whereupon the operation of lowering the priority is carried out.
If a priority level of P=max (R.sub.r, P.sub.m) is employed in outputting the free token, the period of time for which the token circulates through the nodes without being caught is decreased, and therefore the efficiency of the network is increased. Therefore, the probability is large that the token will return to its home node (the node which outputted the token) and its priority thus lowered.
If, in outputting a free token, the priority level is set to P=max (R.sub.r, P.sub.m), the period of time in which the token is circulated without being caught is decreased, with the result that the efficiency of the network is improved.
If the level of priority is changed in the order of "1", "2", "3", and "5", then it is necessary to lower it in the order of "5", "3", "2", and "1". That is, the priority is not lowered from "5" directly to "1". Therefore, if only packets of priority "0" are present in the network, the waiting time which elapses before the transmission-enabling free token is caught is about three times as long as that in the case where the priority is lowered from "5" directly to "1".